package demo2;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-09-03
 * Time: 20:37
 */

import java.sql.SQLOutput;
import java.util.Arrays;

/**
 * 堆排序思想 : 通过堆来进行选择数据, 升序建立大根堆(降序建立小根堆), 通过对堆的向下/向上调整来排序
 */
public class HeapSort {


    /**
     * TODO : 时间复杂度分析, 每一个元素都进行交换到末尾, 并完成剩余元素的向下调整,最终为O(N*logN)
     *        空间复杂度分析, 没有额外开辟空间 O(1)
     *        稳定性分析, 不稳定排序
     *        堆排序使用堆来选数, 从时间复杂度上看, 相对快很多
     */
    public static void heapSort(int[] array) {
        // 1. 升序排列, 建立大根堆
        createMaxHeap(array);
        // 2. 从最后一个位置开始进行排序
        int end = array.length - 1;
        // 最后一个元素和前面的所有元素都进行比较
        while (end > 0) {
            // 建立好大根堆后, 此时堆顶就是最大的元素, 因此将最后一个元素和堆顶交换到最后位置
            // 最终堆顶的最大元素会依次从后向前排序好
            swap(array, end, 0);

            // 长度为 end , 堆顶的元素已经排好了就不在需要调整了
            // TODO : 虽然是 child < len 这个条件, 但防止写错还是先 end--, 防止交换了最后 end 位置元素
            end--;

            // 交换完后, 重新调整成大根堆
            shiftDown(array, 0, end);
        }

    }


    /**
     * 将传入的排序数组进行建堆, 建立大根堆
     * 时间复杂度 : 趋近于 O(N), parent 父节点向前每一个节点都要建立.
     */
    public static void createMaxHeap(int[] array) {
        // 将传入数组调整为一个大根堆, 等同于建堆的过程, 实际并非直接建立了堆
        for (int parent = (array.length - 2) / 2; parent >= 0; parent--) {
            // 从最后一个父节点开始调整
            shiftDown(array, parent, array.length);
        }
    }


    /**
     * 父节点向下调整成大根堆
     * 时间复杂度 : 向下调整, 每一个父节点都要向下调整一定高度(一定层), 高度为 logN
     * 每个元素都调整时, 最终为 O(N + logN)
     */
    private static void shiftDown(int[] array, int parent, int len) {
        int child = (parent * 2) + 1;
        // 当孩子节点超过数组长度时, 表明已经调整结束
        while (child < len) {
            // 1. 判断该 parent 对应的父节点有右孩子, 并且右孩子比左孩子大
            if (child + 1 < len && array[child + 1] > array[child]) {
                // 更改 child 为右孩子
                child++;
            }

            // 2. 孩子节点比父节点大, 交换孩子节点和父节点位置
            if (array[child] > array[parent]) {
                swap(array, child, parent);

                // 3. 更新父节点位置和孩子节点, 看是否需要继续向下调整
                parent = child;
                child = (parent * 2) + 1;
            } else {
                // 本次父节点无需调整
                break;
            }
        }
    }

    private static void swap(int[] array, int index1, int index2) {
        int tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        HeapSort.heapSort(array);
        System.out.println(Arrays.toString(array));
    }
}
